class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        vector<int> v;
        for (int i = 0; i < nums.size(); i++)
        {
            if (v.size() == 0 || nums[i] > v.back()) v.push_back(nums[i]);
            else
            {
                int left = 0, right = v.size() - 1;
                while (left < right)
                {
                    int mid = left + (right - left) / 2;
                    if (v[mid] >= nums[i]) right = mid;
                    else left = mid + 1;
                }
                v[left] = nums[i];
            }
        }
        return v.size();
    }
};
class Solution {
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};
class Solution {
public:
    int fib(int n)
    {
        if (n == 0 || n == 1) return n;
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};
class Solution
{
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    int cnt;
    int ret = 0;
    int m, n;
    vector<vector<bool>> vis;
public:
    int wardrobeFinishing(int _m, int _n, int _cnt)
    {
        cnt = _cnt;
        m = _m; n = _n;
        vis = vector<vector<bool>>(m, vector<bool>(n));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i + j <= cnt && !vis[i][j])
                {
                    ret++;
                    vis[i][j] = true;
                    dfs(i, j);
                }
            }
        }
        return ret;
    }
    int getval(int x, int y)
    {
        int val = 0;
        while (x)
        {
            val += x % 10;
            x /= 10;
        }
        while (y)
        {
            val += y % 10;
            y /= 10;
        }
        return val;
    }
    void dfs(int a, int b)
    {
        for (int i = 0; i < 4; i++)
        {
            int x = a + dx[i];
            int y = b + dy[i];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && getval(x, y) <= cnt)
            {
                ret++;
                vis[x][y] = true;
                dfs(x, y);
            }
        }
    }
};